home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BASE_LIS.H < prev    next >
Text File  |  1992-08-21  |  19KB  |  382 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design and implementation
  13. // Updated: MJF 04/15/89 -- Implemented Base list class.
  14. // Updated: MJF 06/01/89 -- Added const to member function arguments.
  15. // Updated: JCB 06/05/89 -- Fixed sort and merge.
  16. // Updated: JCB 06/20/89 -- Added protected slot, traversal, for use by
  17. //                          next_lunion, next_intersection, etc.
  18. //                          Modified reset() to initialize traversal flag.
  19. // Updated: MJF 06/21/89 -- Changed return types from List& to void or Boolean.
  20. // Updated: LGO 07/03/89 -- Inherit from Generic
  21. // Updated: MJF 08/10/89 -- Changed return values of operator+= etc to List ref
  22. // Updated: LGO 09/07/89 -- Make base-list constructor and destructor inline.
  23. // Updated: MBN 09/20/89 -- Added conditional exception handling
  24. // Updated: MBN 10/10/89 -- Added current_position() method for Iterator<Type>
  25. // Updated: MBN 10/11/89 -- Changed "current_position" to "curpos" and also
  26. //                          "previous_position" to "prevpos"
  27. // Updated: LGO 10/18/89 -- Get rid of the value method.
  28. // Updated: LGO 12/04/89 -- Make binary set operators not inline
  29. // Updated: VDN 02/21/92 -- New lite version
  30. // Updated: JAM 08/14/92 -- removed DOS specifics, stdized #includes
  31. // Updated: JAM 08/14/92 -- modernized template syntax, remove macro hacks
  32. //                          non-template classes Cool_List=>CoolBase_List
  33. //                          CoolList_Node=>CoolBase_List_Node
  34. // Updated: JAM 08/14/92 -- changed all void*s to const void*s; otherwise
  35. //                          lots of assignments would need cast
  36. // Updated: JAM 08/20/92 -- made *_state typedef a nested typedef "IterState"
  37. //                          as per new Iterator convention
  38. //
  39. // A list is simply  made up of a collection  of nodes.   Each node contains  a
  40. // reference  count,  a pointer to  the next  node  in  the  list, and the data
  41. // object.
  42. //
  43. //                      +--------+         +--------+         +--------+
  44. //                      | Ref=2  |         | Ref=1  |         | Ref=2  |
  45. //    +-------+         +--------+         +--------+         +--------+
  46. //    | CoolList--+---+---->| Next --+-------->| Next --+----+--->| Next 0 |
  47. //    +-------+   |     +--------+         +--------+    |    +--------+
  48. //                |     | Data   |         | Data   |    |    | Data   |
  49. //                |     +--------+         +--------+    |    +--------+
  50. //                |                                      |
  51. //    +-------+   |                          +-------+   |
  52. //    | CoolList--+                          | CoolList--+
  53. //    +-------+                              +-------+
  54. //
  55. // The CoolList class is implemented with parameterized types. The specific type of
  56. // the elements in the list is  left  as a  parameter for  the user.  Each list
  57. // declared for elements of a different type  would be a  new class.  A list of
  58. // ints,   CoolList<int>, would expand   to a class  CoolList_int  and  a list strings,
  59. // CoolList<char*>, would expand  to a class CoolList_charp.  Note  that  the lists are
  60. // homogeneous lists where each element of the list is of  the same known type.
  61. // A heterogeneous list  could be maintained  by having the type  be void* or a
  62. // Generic object type where the type of the actual data could be determined.
  63. //
  64. // The CoolList class private data consists of a pointer to a Node class.  The Node
  65. // class contains a reference count, the data object, and a pointer to the next
  66. // node.   The data in each node  of a  list is an object of  type "Type".  The
  67. // CoolList  class is   derived from a  Base  CoolList class.  This file  contains  the
  68. // implementation  of the Base   CoolList  class.  The  CoolList  class can be found in
  69. // List.h
  70. //
  71. // The Base_List class implements the  generic list functionality.  This class
  72. // is not usable as a standalone class, but rather is designed to be derived by
  73. // the CoolList  class.   By providing generic operations   in  a base   class, the
  74. // quantity of code generated for each implementation of the parameterized CoolList
  75. // class is reduced considerably.
  76. //
  77. // All list nodes are  created dynamically and  mangaged with reference counts.
  78. // In the node object,  the reference count  value indicates the number of list
  79. // or node objects pointing to it.  When the value is zero the node  object and
  80. // its data will  be freed.  The  reference count technique  is  used to ensure
  81. // that the node and  its data gets  deallocated  when  the  node is  no longer
  82. // referenced.
  83. //
  84. // The Node class was introduced in order  to maintain the reference count from
  85. // each data  item in  the  list.  The CoolList  class  could have been implemented
  86. // without a pointer to a Node and instead contain a pointer to  the data and a
  87. // pointer to  the next list   item.   However, with  a reference  count it  is
  88. // necessary to have a separate class.  Consider the following set of lists and
  89. // sublists.  Both  List1 and List2  point to  (Node 1,  Node2,  Node3, Node4),
  90. // List3 is a sublist pointing to (Node3,  Node4),  and List4 points to (Node5,
  91. // Node3, Node4).  The  reference count totals for  each node  are shown in the
  92. // ().  Without a separate  node for each data item,  it would be  difficult to
  93. // determine when to deallocate the data when it is no longer referenced.
  94. //
  95. //  +-------+
  96. //  | List1 |---+
  97. //  +-------+   |
  98. //              |
  99. //              |
  100. //              |     +-------+     +-------+     +-------+     +-------+
  101. //              |     |       |     |       |     |       |     |       |
  102. //              +---->| Node1 |---->| Node2 |---->| Node3 |---->| Node4 |---->0
  103. //              |     |  (2)  |     |  (1)  |     |  (3)  |     |  (1)  |
  104. //              |     +-------+     +-------+     +-------+     +-------+
  105. //              |                                     ^
  106. //              |                   +-------+         |   
  107. //  +-------+   |                   | List3 |-------->+
  108. //  | List2 |---+                   +-------+         ^
  109. //  +-------+                                         |
  110. //                                        +-------+   |
  111. //                          +-------+     |       |   |
  112. //                          | List4 |---->| Node5 |---+
  113. //                          +-------+     |  (1)  |
  114. //                                        +-------+
  115. //
  116. // Note that because we have chosen to have a CoolList be comprised of Nodes, it is
  117. // not possible to have generic operations that will  scan a tree  comprised of
  118. // Nodes  themselves containing CoolLists.   This  manifestation is unfortunate but
  119. // necessary to implement heterogenous lists and the reference count scheme.
  120. //
  121. // There   are several constructors available for   the CoolList class.  The CoolList()
  122. // constructor creates a null list,  setting the  node  pointer to  zero.   The
  123. // CoolList(Type& a) constructor creates a list with one data node; a head value of
  124. // a  and a nil  tail.  The CoolList(Type& a,  CoolList& b) constructor creates  a list
  125. // with a head value of a and a b  as the tail.   The CoolList(CoolList& l) constructor
  126. // creates a new list whose head node points to the same node as list l.
  127. //
  128. // The supported operations in the CoolList  class are mirrored closely after those
  129. // in Common Lisp.  There are operations  which return the nth  tail of a list;
  130. // the sublist starting at the nth last node of a list; and  all but the n last
  131. // nodes of a list.  There are operations which return the length of  the list;
  132. // get or set the nth element of the  list; return the  position of a specified
  133. // element; test if the list is empty; clear a list; and test if  two lists are
  134. // equal.   There are  also operations  to search  for  a  specified  member or
  135. // sublist within a list; to reverse the list;  to copy the list; to  append or
  136. // prepend an element or sublist; to set  the tail of  the list; to replace all
  137. // or the first occurence of a specified item on the  list; to remove the first
  138. // occurence  of  a specified item on  the list; to  remove  all duplicates; to
  139. // insert a new item before or after  a specified item on  the list;  to sort a
  140. // list; to merge two lists; to perform the  intersection; union; difference or
  141. // exclusive-or of two lists.
  142. //
  143. // Unlike Common   Lisp,  the  destructive operations  do  not   come  with the
  144. // equivalent non-destructive operations  are  supported.  Most operations will
  145. // be  destructive, such that, the list  object  the message  is performed will
  146. // always  be altered.  A  non-destructive  operation  is easily  done by first
  147. // making a copy of   the  list  object  and  then executing   the  destructive
  148. // operation on that copy.
  149. //
  150. // The CoolList class implements the  notion of a  current position. This is useful
  151. // for  iterating  through the  elements of  a list.   The current position  is
  152. // maintained as a node pointer and is set or reset by all operations affecting
  153. // elements in  the  CoolList  class.  Operations to  reset,  move to the next  and
  154. // previous, find, and get the value at the current position are provided.
  155.  
  156. #ifndef BASE_LISTH        // If the CoolList not defined,
  157. #define BASE_LISTH        // indicate its done now
  158.  
  159. #include <iostream.h>
  160.  
  161. #ifndef MISCELANEOUSH        // If we have not included this file,
  162. #include <misc.h>        // include miscelaneous useful definitions.
  163. #endif
  164.  
  165.  
  166. typedef Boolean (*Compare) (const void*, const void*);    // Pointer to compate function
  167. typedef int (*Predicate) (const void*, const void*);    // Pointer to Predicate
  168. // returns -1 on less, 0 on equal and 1 on greater
  169.  
  170. class CoolBase_List_Node;                // Forward reference class
  171.  
  172. class CoolBase_List_Node {                // Define CoolBase_List_Node class
  173. friend class CoolBase_List;                // Friend class declaration
  174. public:
  175.   inline CoolBase_List_Node*& next_node();        // Return next node pointer
  176.   friend ostream& operator<<(ostream& os, const CoolBase_List&); // Output operator
  177.   
  178. protected:
  179.   int ref_count;                // Reference counter
  180.   CoolBase_List_Node* next;                // Pointer to next node
  181.   
  182.   CoolBase_List_Node();                // Constructor
  183.   virtual ~CoolBase_List_Node();            // Delete as ~CoolList_Node<Type>
  184.   virtual const void* get_data();            // Returns data element 
  185.   virtual void  set_data(const void*);        // Set data element
  186. };
  187.  
  188. // next_node() -- Returns next node pointer.
  189. // Input:         None.
  190. // Output:        The next node pointer
  191.  
  192. inline CoolBase_List_Node*& CoolBase_List_Node::next_node () {
  193.   return this->next;
  194. }
  195.  
  196.  
  197. class CoolBase_List {                // Define the CoolBase_List class
  198. public:
  199.   typedef CoolBase_List_Node* IterState;        // Curpos state for iterator
  200.  
  201.   CoolBase_List() {};                // A Nil CoolBase_List
  202.   virtual ~CoolBase_List();                // Destructor is virtual
  203.   
  204.   inline void reset();                // Reset current position
  205.   inline Boolean next();            // Increment current position
  206.   Boolean prev();                // Decrement current position
  207.   
  208.   Boolean operator==(const CoolBase_List& l) const;    // Equality test
  209.   inline Boolean operator!=(const CoolBase_List& l) const; // Inequality test
  210.   
  211.   void tail(CoolBase_List& l, int n = 1);        // Sets l to the nth tail/cdr
  212.   void last(CoolBase_List& l, int n = 1);        // Sets l to the n last nodes
  213.   void but_last(CoolBase_List& l, int n = 1);    // Sets l to all but n last
  214.   
  215.   void clear();                    // Removes all nodes 
  216.   inline Boolean is_empty();            // Any nodes in List?
  217.   int length();                    // Returns node count in List
  218.   int position();                // Returns current position
  219.   
  220.   Boolean search(const CoolBase_List& l);        // SubList search
  221.   
  222.   // returns true if THIS CoolBase_List contains the specified subList
  223.   // and sets CoolBase_List l to a subList in THIS List starting at the 1st occurence
  224.   // of CoolBase_List s
  225.   Boolean sublist(CoolBase_List& l, const CoolBase_List& s);
  226.   
  227.   void copy(const CoolBase_List& l);            // Copy l into *this
  228.   void reverse();                // Reverses order of elements
  229.   Boolean prepend(const CoolBase_List& l);        // Prepends l to start of List
  230.   Boolean append(const CoolBase_List& l);        // Appends  l to end of List
  231.   
  232.   Boolean set_tail(const CoolBase_List& l, int n = 1); // rplacd a l
  233.   Boolean remove_duplicates();              // Removes duplicate elements
  234.   
  235.   void set_intersection(const CoolBase_List& l);    // Intersection of two Lists
  236.   void set_union(const CoolBase_List& l);        // Union of two Lists
  237.   void set_difference(const CoolBase_List& l);    // Difference of two Lists
  238.   void set_xor(const CoolBase_List& l);        // XOR of two Lists
  239.   
  240.   Boolean next_intersection(const CoolBase_List& l); // Current position intersect
  241.   Boolean next_union(const CoolBase_List& l);    // Current position union
  242.   Boolean next_difference(const CoolBase_List& l);    // Current position difference
  243.   Boolean next_xor(const CoolBase_List& l);        // Current position XOR
  244.   
  245.   void describe(ostream& os);            // Describes structure of List
  246.   
  247.   friend ostream& operator<<(ostream& os, const CoolBase_List& l); // Output 
  248.   /*##inline*/ friend ostream& operator<<(ostream& os, const CoolBase_List* l); 
  249.  
  250. protected:
  251.   CoolBase_List_Node* node_ptr;            // Pointer to first node
  252.   CoolBase_List_Node* curpos;            // Maintains current position
  253.   CoolBase_List_Node* prevpos;            // Performance hack to previous
  254.   Boolean traversal;                // Traversal flag for curpos
  255.   
  256.   virtual CoolBase_List* new_list(CoolBase_List_Node*);    // Creates a new CoolBase_List from node
  257.   virtual CoolBase_List_Node* insert_before_node(const void* v, CoolBase_List_Node* next_np);
  258.   virtual CoolBase_List_Node* insert_after_node(const void* v, CoolBase_List_Node* prev_np) const;
  259.   
  260.   virtual Boolean compare_data(const void*, const void*) const;
  261.   virtual void output_data(ostream&, const CoolBase_List_Node*) const;
  262.   
  263.   CoolBase_List_Node* copy_nodes() const;        // Returns copy of nodes
  264.   inline void reference(CoolBase_List_Node*);    // Increments reference count
  265.   inline void dereference(CoolBase_List_Node*);    // Decrements reference count
  266.   // And if zero, deletes node
  267.   void CoolBase_List::free_nodes(CoolBase_List_Node* np); // Deletes nodes
  268.   
  269.   CoolBase_List* operator=(const CoolBase_List& l);    // Assignment List1 = List2;
  270.   CoolBase_List_Node* operator[](int n);        // X = l[n];
  271.   
  272.   int position(const void* x);            // Returns 0-relative index 
  273.   virtual Boolean do_find(CoolBase_List_Node* np, const void* x, // Used by find
  274.               CoolBase_List_Node*& cp, CoolBase_List_Node*& pp) const;
  275.   // returns true if THIS CoolBase_List contains element x and 
  276.   // sets CoolBase_List l to a subList in THIS List starting at the first occurence of x
  277.   Boolean member(CoolBase_List& l, const void* x);
  278.   
  279.   Boolean push(const void* x);            // Adds X to head of THIS List
  280.   Boolean push_new(const void* x);        // Push(X) if not in THIS List
  281.   Boolean push_end(const void* x);        // Adds X at end of THIS List
  282.   Boolean push_end_new(const void* x);        // push_end(x) if not in List
  283.   
  284.   CoolBase_List_Node* pop();                // Removes/returns head node
  285.   CoolBase_List_Node* remove();            // Removes item at curpos
  286.   Boolean remove(const void* x);        // Removes first occurence
  287.   
  288.   Boolean replace(const void*, const void*);    // Replace first
  289.   Boolean replace_all(const void*,const void*); // Replace all
  290.   
  291.   void sort(Predicate f);            // Sort List using predicate
  292.   void merge(const CoolBase_List& l, Predicate f);    // Merge List w/ sort predicate
  293.   
  294.   Boolean insert_before(const void* new_item);    // Insert item before curpos
  295.   Boolean insert_after(const void* new_item);    // Insert item after curpos
  296.   
  297.   Boolean insert_before(const void*,const void*); // Insert item before
  298.   Boolean insert_after(const void*, const void*); // Insert item after
  299.   
  300.   void value_error (const char*);        // Raise exception
  301.   void get_error (const char*, int);        // Raise exception
  302.   void before_error (const char*);        // Raise exception
  303.   void after_error (const char*);        // Raise exception
  304.   void bracket_error (const char*, int);    // Raise exception
  305.   void pop_error (const char*);            // Raise exception
  306.   void remove_error (const char*);        // Raise exception
  307.   void va_arg_error (const char*, int);        // Raise exception
  308. };
  309.  
  310.  
  311. // reference () -- Increments the reference count of a node pointer
  312. // Input:          The node pointer to be referenced.
  313. // Output:         None.
  314.  
  315. inline void CoolBase_List::reference(CoolBase_List_Node* np) {
  316.   if (np != NULL) np->ref_count++;
  317. }
  318.  
  319.  
  320. // dereference() -- Decrements the reference count of the node pointer and
  321. //                  deallocates storage if no longer referenced.
  322. // Input:           The node pointer to be dereferenced.
  323. // Output:          None.
  324.  
  325. inline void CoolBase_List::dereference(CoolBase_List_Node* np) {
  326.   if (np != NULL && --(np->ref_count) <= 0)
  327.     this->free_nodes(np);
  328. }
  329.  
  330.  
  331. // reset() -- sets current position to NULL
  332. // Input:     None.
  333. // Output:    None.
  334.  
  335. inline void CoolBase_List::reset() {
  336.   this->curpos = NULL;
  337.   this->prevpos = NULL;
  338.   this->traversal = TRUE;
  339. }
  340.  
  341.  
  342. // next() -- Increment current position. If NULL, set it to first.
  343. // Input:    None.
  344. // Output:   TRUE or FALSE.
  345.  
  346. inline Boolean CoolBase_List::next() {
  347.   register CoolBase_List_Node* cp = this->curpos;
  348.   if (cp == NULL)                // Current position valid?
  349.     cp = this->node_ptr;            // Set curpos to head node
  350.   else
  351.     (cp = cp->next);                // Advance to next position
  352.   return ((this->curpos = cp) != NULL);        // Return status
  353. }
  354.  
  355.  
  356. // operator!=() -- Returns TRUE if data in THIS CoolBase_List and the not the same
  357. // Input:          A CoolBase_List reference.
  358. // Output:         TRUE or FALSE.
  359.  
  360. inline Boolean CoolBase_List::operator!=(const CoolBase_List& l) const {
  361.   return !this->operator==(l);
  362. }
  363.  
  364.  
  365. // is_empty() -- Indicates node presence in CoolBase_List
  366. // Input:        None.
  367. // Output:       TRUE or FALSE.
  368.  
  369. inline Boolean CoolBase_List::is_empty() {
  370.   return this->node_ptr == NULL;
  371. }
  372.  
  373. // operator<<() -- Overload output operator for CoolBase_List objects
  374. // Input:          An output stream reference and CoolBase_List pointer.
  375. // Output:         An output stream reference.
  376.  
  377. inline ostream& operator<<(ostream& os, const CoolBase_List* l) {
  378.   return operator<<(os, *l);
  379. }
  380.  
  381. #endif                        // End of BASE_LISTH
  382.